/**
 * @author CHENTAIWEN
 * @create 2022/9/20 15:42
 */
public class KMP {

    public static void main(String[] args) {

        String t = "ACAABCDBCABABAABCDBA";
        String p = "ABCABA";
//        -1,-1,-1,0,1,2
//        A B C A B A
        int[] next = getNext(p);
        for (int i = 0; i < next.length; i++) {
            System.out.print(next[i] + ",");
        }
        System.out.println();
        System.out.println(getKMP(t, p));
    }

    public static int getKMP(String t, String p) {
        int index = -1;
        int pLength = p.length();
        int tLength = t.length();
        // 模式串的长度当然要小于等于主串长度
        if (pLength <= tLength) {
            int[] next = getNext(p);
            int k = -1;
//            K+1表示重复前缀长度 k=-1表示没有重复前缀
            for (int i = 0; i < tLength; i++) {
                // 当前字符和最长前缀下一个字符不同，则往前回溯
                while (k > -1 && t.charAt(i) != p.charAt(k + 1)) {
                    // 已经比较了位置k+1的字符不同，往前回溯的话应该往k位置，k位置的最长前缀的位置k=next[k]
                    k = next[k];
                    System.out.println(k);
                }
                System.out.print(t.charAt(i) + " " + p.charAt(k + 1));
                if (t.charAt(i) == p.charAt(k + 1)) {
                    // 这个k+1,其实就是模式串的下一个字符下标
                    k = k + 1;
                    System.out.print(" " + k + "\n");
                    if (k == pLength - 1) {
                        index = i - pLength + 1;
                        break;
                    }
                }
            }
        }
        return index;
    }

    public static int[] getNext(String p) {
        int[] next = new int[p.length()];
        next[0] = -1;
        int k = -1;

        for (int i = 1; i < p.length(); i++) {
            // 当前字符和最长前缀下一个字符不同，则往前回溯
            while (k > -1 && p.charAt(i) != p.charAt(k + 1)) {
                // 已经比较了位置k+1的字符不同，往前回溯的话应该往k位置，k位置的最长前缀的位置k=next[k]
                k = next[k];
            }
            // 当前字符和当前字符前面字符串的最长前缀的下一个字符相同，则k+1
            if (p.charAt(i) == p.charAt(k + 1)) {
                k = k + 1;
            }
            next[i] = k;
        }
        return next;
    }

}

